1. Field of the Invention
The present invention generally relates to a method and system for watermarking of images as printed with digital printers, and more particularly to a method and system such as printers or other graphical media including screens of various sorts, that can only display a limited number of colors at each pixel.
2. Description of the Related Art
An xe2x80x9cimperceptible watermarkxe2x80x9d (hereafter xe2x80x9cwatermarkxe2x80x9d for short), is defined herein as an alteration of the data set which is mostly not perceptible to a human (i.e., the watermark should be (mostly) invisible), but can be recognized by a machine such as a computer. The general principle of such a watermark has been disclosed, for instance, in xe2x80x9cDigital Watermarking for High-quality Imagingxe2x80x9d, by M. M. Yeung, F. C. Mintzer, G. W. Braudaway, and A. R. Rao, Proceedings of the IEEE Signal Processing Society Multimedia Workshop, Princeton, N.J., 1997.
In the above-mentioned paper, the emphasis is on computer images and other images where each pixel contains information described by one or more real numbers (i.e., all together 8 or more bits of information per pixel for black and white, and several times this amount for color, depending on the number of basic colors being used, usually 4 to 6).
However, hitherto the present invention, there have been few methods or techniques known for producing a digital watermark which is mostly targeted at prints and other images where each pixel contains information described by one or more small integer numbers, or by one or more rational numbers with a small denominator (i.e., the denominator is smaller than 16; altogether usually 4 or less bits of information per pixel for black and white, and several times this amount for color, depending on the number of basic colors being used, usually 4 to 6).
Hence, when building watermarks for electronic images, one is greatly helped by there being a lot of information per pixel. For example, one can hide the watermarks in the least significant bits at some or all pixels. However, when dealing with digital prints, one loses most of this freedom as there is anywhere from one to a small number (usually at most four) digits of information (per color) per pixel. This problem was solved for instance in xe2x80x9cCounterfeit Detection Methodxe2x80x9d by Turho, Xerox Disclosure Journal Vol. 20 No 6 November/December 1995, in U.S. Pat. No. 5,488,664 to Shamir, and in U.S. Pat. No. 5,734,752 to Knox. Both Shamir and Knox provide methods allowing visual recognition of a watermark by comparing a print to a second print, the second print being printed on a transparent medium. The inventions of Shamir and Knox both use pixel blocks, but in a quite different manner.
That is, Knox also uses pixel blocks, larger than the ones used by Shamir, although this use of pixel blocks is not stated explicitly. More precisely, Knox uses two or more different dithering masks with identical boundaries but different, stochastic, interior parts. The part of a half-toned image where a given mask has been used can be thought of as a xe2x80x9cpixel blockxe2x80x9d. It is noted that the methods in Shamir and Knox, of using a transparent medium to visually recognize a watermark, can be used as a way to implement the verification stage of the present invention described below.
However, this implementation would not be very practical as some substantial amount of computation must be performed to verify a public signature, whereas the inventions of Shamir and Knox are aimed at helping in situations only requiring moderate levels of security where less information needs to be checked to accept a document or other object as authentic.
Problems of the conventional techniques to which the present invention is aimed at solving include:
1) For watermarks which are being used for the protection of the integrity and originality of an image, in contexts where high levels of security are required, it is advantageous, for both practicality and increased security, that the watermark be designed using public key cryptography. Part of the problem of using a public key infrastructure (PKI) for images is to find means to stably read information out of the image in order to check a signature.
More precisely, this problem is trivial to anyone versed in the art of cryptography, as long as the image is kept and circulated only in electronic form, as one can then reasonably hope that the information content of the image is invariant in time and predictable from what can be known at the time of the signature.
However, when an image is printed, the information is less stable, and even the problem of recovering the precise content of each pixel is difficult because the image must be perfectly placed on a scanner glass, as the pixels are quite small. A solution to this problem in the case of high quality printed images, as can be provided for instance with offset printing or dye sublimation, is disclosed in U.S. patent application Ser. No. 09/398,203, to G. Aggarwal et al., filed Sep. 17, 1999. The problem which is considered in the present invention is halftoned images, as provided by digital or multitone printers as well as files with similar formats, as described below.
2) When it is desirable to have the precise halftone of a image to be preserved, the halftoned part can be stored and circulated, for instance on the world-wide-web (WWW). Also, with the increasing use of smaller computing devices with limited display capabilities, halftone images have increased room in the new electronic age.
One problem in keeping an image in halftone form is that halftones are hard to compress. It would be advantageous to hide a small copy of a halftoned image in the halftoned image itself. This would allow a user to decide, for example, if the full image is worthwhile receiving using information which needs not be sent again in case the decision is made of receiving the full image.
In view of the foregoing and other problems, disadvantages, and drawbacks of the conventional methods and structures, an object of the present invention is to provide a method and system for using such watermarks which solve the above-mentioned problems.
Another object is to provide watermarks for digital prints so as to provide the requisite security for authenticating documents.
Below, first, the watermarks solving the above-mentioned problems, will be described assuming that scanning of the printed images can be done very exactly without difficulty.
Then, it will be described how to implement the invention to overcome this further difficulty. The present invention will be presented in the context of digital black and white printers. Adaptation to color and multitone would be obvious to anyone versed in the art taking the present application as a whole.
In a first aspect, a method (and system) of watermarking a half-toned image, includes grouping pixels of an image into blocks each containing a plurality of pixels, using as many gray levels as there are pixels in a block to halftone the image formed in the same blocks of pixels, based on a data set formed by the gray levels of the blocks of the halftoned image, generating at least one of a digital signature and a compressed version of the image, to form a generated unit, and inserting the generated unit in the halftoned image to form the watermark, by selecting how a predetermined number of pixels in a block are placed in the block.
In a second aspect, a method of watermarking a digital print, includes reserving a space N0(m,N) in a memory to print a half-toned version of an image, where 1xe2x89xa6mxe2x89xa6Hxe2x80x2 and 1xe2x89xa6nxe2x89xa6Vxe2x80x2, reserving a smaller space for receiving a matrix M(h, v), the smaller space being determined by the size h0-by-v0 of the pixel blocks, determining, based on a size of the pixel blocks, a list of gray levels to be used, the list representing that either 0, 1, 2, . . . , h0.v0 pixels can be black in the pixel blocks, using, by a half-toning algorithm, the list of gray levels, and determining the image I={I(i,j)} to be printed, wherein each element I(i,j), with 1xe2x89xa6ixe2x89xa6Himage and 1xe2x89xa6jxe2x89xa6Vimage, is a gray level g, where g is a real number between 0 and 1.
In a third aspect, a method of embedding a watermark in an image, includes forming a watermark which contains at least one of a digital signature and a small copy of the image, and embedding the watermark in a halftoned image of the image.
In a fourth aspect, a system for watermarking a half-toned image includes means for grouping pixels of an image into blocks each containing a plurality of pixels, means for using as many gray levels as there are pixels in a block to halftone the image formed in the same blocks of pixels, means for, based on a data set formed by the gray levels of the blocks of the halftoned image, generating at least one of a digital signature and a compressed version of the image, to form a generated unit, and means for inserting said generated unit in the halftoned image to form said watermark, by selecting how a predetermined number of pixels in a block are placed in the block.
Further, a program storage medium is provided for storing program steps of the inventive methods.
With the unique and unobvious features of the present invention, a method and system are provided which employ a watermark in a digital print, so as to provide the requisite security for authenticating documents, and regardless of whether the image was scanned correctly or not. The invention also provides means to embed a compressed version of an image in the digital print of the image.